import java.util.*;

public class project {
    public boolean checkAlmostEquivalent(String word1, String word2) {
        int[] arr=new int[26];
        for(int i=0;i<word1.length();i++){
            char ch=word1.charAt(i);
            char c=word2.charAt(i);
            arr[ch-'a']++;
            arr[c-'a']--;
        }
        for(int a : arr){
            if(a>3||a<-3){
                return false;
            }
        }
        return true;
    }











    public int integerReplacement(int n) {
        if(n==1){
            return 0;
        }
        if(n%2==0){
            return 1+integerReplacement(n/2);
        }
        return 2+Math.min(integerReplacement(n/2),integerReplacement(n/2+1));
    }














    public int nearestValidPoint(int x, int y, int[][] points) {
        int len=points.length;
        int min=Integer.MAX_VALUE;
        int ret=-1;
        for(int i=0;i<len;i++){
            if(points[i][0]==x||points[i][1]==y){
                int tmp=getmax(points[i],x,y);
                if(tmp<min){
                    min=tmp;
                    ret =i;
                }
            }
        }
        return ret;
    }
    public int getmax(int[] arr,int x,int y){
        return Math.abs(arr[0]-x)+Math.abs(arr[1]-y);
    }












    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int len=nums.length;
        int min=Integer.MAX_VALUE;
        for(int i=0;i<len-k+1;i++){
            min=Math.min(min,nums[k+i-1]-nums[i]);
        }
        return min;
    }








    public boolean isPrefixString(String s, String[] words) {
        StringBuilder sb=new StringBuilder();
        for(String str : words){
            sb.append(str);
            if(sb.toString().equals(s)){
                return true;
            }
        }
        return false;
    }












    public boolean isThree(int n) {
        int sum=0;
        for(int i=2;i<=n;i++){
            if(n%i==0){
                sum++;
            }
        }
        return sum==2;
    }











    public int countTriples(int n) {
        Set<Integer> set=new HashSet<>();
        for(int i=1;i<=n;i++){
            set.add(i*i);
        }
        int count=0;
        for(int i=1; i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(set.contains(i*i+j*j)){
                    count+=2;
                }
            }
        }
        return count;
    }














    public boolean makeEqual(String[] words) {
        int len=words.length;
        Map<Character,Integer> map=new HashMap<>();
        for(String str : words){
            for(char ch : str.toCharArray()){
                map.put(ch,map.getOrDefault(ch,0)+1);
            }
        }
        for(Map.Entry<Character,Integer> entry : map.entrySet()){
            if((entry.getValue()%len)!=0){
                return false;
            }
        }
        return true;
    }













    public boolean findRotation(int[][] mat, int[][] target) {
        int len=mat.length;
        boolean b1=true,b2=true,b3=true,b4=true;
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(mat[i][j]!=target[i][j]){
                    b1=false;
                }
                if(mat[len-j-1][i]!=target[i][j]){
                    b2=false;
                }
                if(mat[j][len-i-1]!=target[i][j]){
                    b3=false;
                }
                if(mat[len-i-1][len-j-1]!=target[i][j]){
                    b4=false;
                }
            }
        }
        return b1||b2||b3||b4;
    }














    public boolean isCovered(int[][] ranges, int left, int right) {
        Set<Integer> set=new HashSet<>();
        for(int i=0;i<ranges.length;i++){
            int a=ranges[i][0];
            int b=ranges[i][1];
            while(a<=b){
                set.add(a);
                a++;
            }
        }
        while(left<=right){
            if(!set.contains(left)){
                return false;
            }
            left++;
        }
        return true;
    }
}
